1. Field of the Invention
The present invention relates to the field of image representation. More particularly, the present invention relates to a method of identifying visual attributes of an image and transforming them into mathematical models.
2. Background Information
Analysis and processing of digital images plays an important role in nearly all disciplines of modem economics. From medical imaging to industrial quality control and diagnostics to entertainment and advertising, efficient image analysis, representation and processing is the primary component of the overall imaging system performance.
Some conventional methods of image analysis rely on extracting specific lines from the original images (referred to as xe2x80x9cedgesxe2x80x9d), which separate distinct image areas of different brightness (or color). These specific lines may also be referred to as xe2x80x9cridges,xe2x80x9d which are narrow strips, visually separated from the background by their brightness or color. Use of edge and ridge technology is described, for example, in relevant sections of A. Blake and M. Isard, xe2x80x9cActive Contoursxe2x80x9d (1998); J. Foley, et al., xe2x80x9cComputer Graphics: Principles and Practicexe2x80x9d (1997); and R. Gonzales and P. Wintz, xe2x80x9cDigital Image Processingxe2x80x9d (1987).
Generally speaking, the importance of such xe2x80x9cline-shapedxe2x80x9d image patterns, both for human visual perception and efficient automated image analysis, processing and representation, is well recognized in the field. However, the existing methods provide only partial information on the geometric and brightness structures relating to the line-shaped patterns. This partial information is insufficient for adequate image analysis of patterns. As applied to accurate image reproduction and representation, the conventional methods based on edge/ridge partitions are inadequate, especially with respect to high resolution images of the real world.
There are two main reasons for the general failure of conventional methods. First, the edges and ridges are detected only as geometric lines on the image. They are formed by original pixels (or by pixels in a finer grid), or they are approximated by splines. Such limited geometric representation does not simultaneously capture brightness or color patterns along the detected lines. Without the brightness or color pattern information, visually authentic capturing and reconstruction of line-shaped xe2x80x9cimage formsxe2x80x9d is not possible. Therefore, use of the conventional methodology in applications requiring realistic human visual perception of the image or high resolution analysis of medical, industrial and other commercially significant images is extremely limited.
The inadequate treatment of brightness patterns along line-shaped image forms results from difficulties associated with capturing such information. For example, whether or not a consistent brightness pattern exists along a given line is unpredictable. Typically, from a global perspective, both brightness and geometric shapes vary along any one line to such a large extent that direct comparison between any two distinct points on the line is virtually impossible. Furthermore, even for a line having somewhat uniform brightness and geometric characteristics, empirical determination of the corresponding brightness pattern is not possible by the conventional methods, because it requires explicit comparison of brightness data at different points along the line.
Second, edges and ridges as captured by conventional methods form only part of the visually significant line-shaped image patterns. Human visual experience demonstrates that much more complicated patterns than simply edges and ridges are perceived in line-shaped image forms. Conventional methods cannot recognize these more complicated forms.
In U.S. Pat. No. 5,510,838, to YOMDIN, et al., a method is disclosed for image representation by four types of models: edges, ridges, hills and background. Distinctive types of brightness profiles associated with the edge and ridge models are disclosed therein. However, the method of U.S. Pat. No. 5,510,838 presents a number of practical disadvantages. For example, the edge and ridge detection (and, in particular, detection of corresponding brightness profiles) is treated as an integral part of overall image representation. Consequently, isolated application of edge and ridge detection is difficult. Also, the method disclosed in U.S. Pat. No. 5,510,838 requires that the original image be subdivided into an artificial grid of cells, each having a size of 6 to 48 pixels. The cells in these grids must be processed independently. Such subdivision contradicts the global nature of edges and ridges, reduces the visual quality of the resulting model-based image and renders many image analysis and processing applications virtually impossible.
U.S. Pat. No. 5,510,838 has additional practical problems, common to conventional image representation methods. First, the shape of the brightness profiles is determined a priori, and permits only limited adjustment to the actual image pattern. Second, the method cannot be used for empirical determination of actual, more complicated brightness profiles present on the image. Also, the resolution of the detection method is generally limited due to the use of second degree polynomial approximations on 4xc3x974 pixel windows.
Some of these problems are addressed in U.S. Pat. No. 5,960,118, to BRISKIN, et al. For example, an extended variety of brightness profiles is disclosed in this document. Also, the resolution of the detection method is improved by incorporating 3xc3x973 pixel windows in the original polynomial approximation. The patent also describes a limited method for empirical profile detection, dependant on the assumption that the profile is constant along the subject line (which is not the case for most brightness profiles). Furthermore, U.S. Pat. No. 5,960,118 still does not allow for application of edge and ridge detection separately from the full image representation process. U.S. Pat. No. 5,960,118 also does not eliminate the necessity of subdividing images into cells.
In view of the above, the present invention through one or more of its various aspects and/or embodiments is presented to accomplish one or more objectives and advantages, such as those noted.
The present invention overcomes the shortcomings of the existing techniques of image analysis and processing based on edge and ridge detection. It provides a method for identification of general characteristic lines on an image, as well as the signatures and fitting transformations corresponding to each characteristic line. The signatures simultaneously capture the brightness (or color) pattern along detected lines and the fitting transformations consolidate similar brightness and geometric patterns, while maintaining visual integrity of the overall image.
The present invention describes a method for empirical determination of an actual brightness cross-section along any given line. The present invention also provides an efficient representation of characteristic lines by mathematical models. The method enables a number of image analysis implementations, including visual quality inspections, pattern detections and sensor calibrations, based on the analysis of characteristic lines and their signatures. Furthermore, all types of characteristic lines are accurately captured.
All aspects of the invention include steps that are implementable by a computing device, without input from a user (i.e., automatic), or by a computing device in combination with an interface device, with input from the user (i.e., interactive). The invention also includes any combination of automatic and interactive implementations.
An aspect of the invention provides for representing an image by identifying one or more characteristic lines of the image, each characteristic line being a line along which a visual pattern repeats itself. A central line, which corresponds to and approximates the shape of the characteristic line, is determined. A cross-section, consisting of one or more geometric and one or more brightness parameters, at each point along the central line is also determined. Then, a basis cross-section representative of the characteristic line is determined and transformed to the cross-sections of the points along the central line. A characteristic line model representing the characteristic line of the image is assembled from the central line, the basis cross-section and the transformed cross-sections. The characteristic line model is stored, transmitted or processed further, depending on the implementation. The image may be a digital or analog image.
In another aspect of the invention, an image is represented by identifying one or more characteristic lines of the image, each characteristic line being a line along which a visual pattern repeats itself. A central line corresponding to the characteristic line and approximating the shape of the characteristic line shape is determined. Visual patterns along the central line are then identified. A basis signature representative of the characteristic line is determined and this basis signature is transformed to approximate a repetition of the visual pattern along the central line. A characteristic line model representing the characteristic line is assembled, consisting of the central line, the basis signature and the transformation of the basis signature. The characteristic line model is stored, transmitted or processed further, depending on the implementation.
According to still another aspect of the invention, an image is represented by first detecting edges on the image and adjacencies among the detected edges. The common adjacencies among the edges are interpreted as characteristic lines. A central line corresponding to each of the characteristic lines is then determined, the central line approximating the shape of the characteristic line and consisting of a number of points. Cross-sections corresponding to each of the points along each central line is detected. Each cross-section consists of at least one geometric parameter and at least one brightness parameter.
This process can also be implemented by detecting ridges and their associated adjacencies on the image, in addition to edges. The common adjacencies among the ridges are interpreted as characteristic lines. A central line corresponding to each of the characteristic lines is determined, the central line approximating the shape of the characteristic line and consisting of a number of points. Cross-sections corresponding to each of the points along each central line is detected. Each cross-section consists of one or more geometric parameters and one or more brightness parameters.
The image representation is further accomplished according to an aspect of the invention by subdividing each of the detected edges into spline segments. Each spline segment is evaluated, identifying adjacent spline segments. At least one adjacency interval on edge components is identified, which corresponds to the detected edges.
In an aspect of the invention, the adjacent spline segments are identified by first scanning all of the spline segments. For each one of the spline segments, adjacent spline segments are identified according to the following criteria: Adjacent spline segments contain at least one point that is less than or equal to a predetermined distance from the one spline segment and have a direction that forms an angle with the direction of the one spline segment which is less than or equal to a predetermined value. An adjacent spline segment also contains a midpoint that, when joined by an adjacency pointer with the midpoint of the one spline segment, results in an adjacency pointer having a direction that forms an angle with the direction of each of the joined spline segments which differs from (e.g.) 90 degrees by less than or equal to a predetermined value. The comparison is repeated for each of the scanned spline segments until they all have a corresponding set of adjacent spline segments.
According to another aspect of the invention, an image is represented by detecting edges on the image and subdividing the edges into corresponding spline segments. Each of the spline segments is evaluated and the adjacent spline segments are identified. The midpoint of each evaluated spline segment is then connected by an adjacency pointer with the midpoint of each of its corresponding adjacent spline segments, creating adjacency couples. Adjacency intervals of the image are identified as continuous chains of the adjacent couples. A central point of each adjacency pointer within each adjacency couple is identified and the central points are joined within each adjacency interval to form a central line corresponding to a characteristic line.
Once each central line is formed, the cross-sections corresponding to the points along the central line are detected. The cross-sections consist of at least one geometric parameter and at least one brightness parameter. A basis cross-section representative of the associated characteristic line is determined. The basis cross-section is transformed to the cross-sections of the points on the central line and a corresponding fitting path is determined. A characteristic line model representing the characteristic line is assembled, the characteristic line model consisting of at least the data representing the central line, the basis cross-section and the fitting path. The characteristic line model may then be stored, transmitted or processed.
In one aspect of the invention, adjacent spline segments corresponding to each of the evaluated spline segments are identified by first scanning all of the spline segments and identifying for each scanned spline segment the other spline segments that meet predetermined criteria. In particular, for spline segments to be considered adjacent to another of the spline segments, such a spline segment should contain at least one point that is less than or equal to a predetermined distance from the other spline segment and should have a direction that forms an angle with a direction of the other spline segment less than or equal to a predetermined value. Furthermore, the spline segment should contain a midpoint that, when joined by an adjacency pointer with a midpoint of the other spline segment, results in an adjacency pointer having a direction that forms an angle with the direction of each of the joined spline segments which differs from (e.g.) by 90 degrees less than or equal to a predetermined value. This comparison is repeated for each of the scanned spline segments.
In other aspects of the invention, the cross-sections are detected in alternative ways. One way is to identify scanning points at equal intervals along the central line of a characteristic line and project a line segment orthogonal to the central line at each of the scanning points. Characteristic points are identified on the orthogonal line segment at each point where the orthogonal line segment intersects the margin of the edges forming the characteristic line. An image brightness is sampled at each of the characteristic points on the orthogonal line segment. The cross-section of each orthogonal line segment is then approximated by a cross-section of the edges corresponding to the sampled image brightness.
In an alternative embodiment, the cross-sections are detected by subdividing the central line into subpieces, each having a predetermined length. Pixels located within a characteristic strip corresponding to each of the subpieces are identified. These pixels are defined at least according to their respective distances from the central line and brightness parameters. A cross-section at each of the subpieces is then derived based on the defined pixels.
The cross-sections are further refined by forming a quadratic difference between each derived cross-section and the cross-section derived from the next subpiece. The quadratic differences with respect to the parameters of a fitting transformation associated with the cross-section are minimized. A minimized fitting transformation of each derived cross-section and the cross-section derived from the next one of the subpieces is identified. Multiple fitting transformations are composed from these minimized fitting transformations and interpolated along the corresponding line segment. A fitting path is derived from the interpolated fitting transformations and each of the pixels are redefined according to its distance from the central line corrected according to the fitting path and one of its brightness or color parameter corrected according to the fitting path. A corrected cross-section is then derived at each of the subpieces based on the redefined pixels. In an aspect of the invention, the central lines are corrected by identifying a geometrically central point of the associated corrected cross-section and applying the fitting path to the central point.
In another aspect of the invention, an image, having an original size, is represented by first reducing the image from the original size. At least one characteristic line of the reduced image is identified, each characteristic line being a line on the image along which a visual pattern repeats itself. The reduced image is then re-scaled to the original size and a central line is determined corresponding to the characteristic line. The central line approximates the shape of the identified characteristic line and consists of a number of points. Then, consistent with other aspects of the invention, visual patterns along the central line are then identified. A basis signature representative of the characteristic line is determined and this basis signature is transformed to approximate a repetition of the visual pattern along the central line. A characteristic line model representing the characteristic line is assembled, consisting of the central line, the basis signature and the transformation of the basis signature. The characteristic line model is stored, transmitted or processed further, depending on the implementation.
Further, according to a related aspect of the invention, the central line of the re-scaled image is identified as a candidate central line. A characteristic strip associated with the candidate central line is determined. The characteristic strip includes portions of the image adjacent to the candidate central line. Image patterns are detected within the characteristic strip. It is then determined whether each of the image patterns within the characteristic strip repeats along the central line. If the image patterns within the characteristic strip do not repeat along the central line, the candidate central line is discarded as not corresponding to a characteristic line. Otherwise, the candidate central line is accepted and each of the image patterns is separated, a signature is identified and a geometric transformation that fits the signature to the repetitions of the pattern along the candidate central line is determined. A signature and a fitting sequence corresponding to the candidate central line are then approximated.
In another embodiment of the invention, an image is represented by identifying an empirical cross-section of at least one point of a line on the image. It is determined whether the line approximates the shape of a uniform characteristic line. If so, a fitting path, a corrected cross-section and a central line of the uniform characteristic line are identified accordingly.
Other aspects of the invention involve implementation of image representation by a computing apparatus. The computing apparatus includes a computing device that executes computer readable code, an input device that receives the digital image and interfacing with a user, at least one data storage device that stores computer data, and a programming code reading device that reads computer executable code. The computing device is in communication with the input device, the data storage devices and the programming code reading device.
According to one aspect of the invention involving computer apparatus implementation, the computer executable code instructs the computing device to identify at least one characteristic line of the image. Each characteristic line includes a line along which a visual pattern repeats itself. The computing device determines a central line corresponding to the characteristic line, the central line approximating the shape of the characteristic line and consists of a number of points. The computing device then determines a cross-section at each of the points along the central line, determines a basis cross-section representative of the characteristic line and transforms the basis cross-section to the cross-sections of the points along the central line. The cross-section includes at least one geometric parameter and at least one brightness parameter. Data representing the characteristic line, the central line, the cross-section and the transforms of the cross-section are stored in at least one data storage device. Also, the characteristic lines and the central line corresponding to each characteristic line may be identified by a user via the input device.
In another aspect of the invention, computer executable code instructs the computing device to identify at least one characteristic line of the image, each characteristic line including a line along which a visual pattern repeats itself. The computer executable code further instructs the computing device to determine a central line corresponding to the characteristic line, identify a plurality of patterns along the central line, determine a basis signature representative of the characteristic line and transform the basis signature to approximate a repetition of the visual pattern along the central line. The central line approximates the shape of the characteristic line. Data representing the characteristic line, the central line, the patterns, the basis signature, and the transforms of the cross-section are stored in at least one data storage device. The characteristic lines, as well as the central line and visual pattern corresponding to each characteristic line, may be identified by the user via the input device.
In another aspect of the invention, computer executable code causes the computing device to reduce the image from an original size and to identify at least one characteristic line of the reduced image. The characteristic line is a line along which a visual pattern repeats itself. The computing device then re-scales the reduced image to the original size, and determines for the re-scaled image a central line corresponding to the characteristic line. The central line approximates the shape of the characteristic line and consists of a number of points. The computing device then identifies patterns along the central line, determines a basis signature representative of the characteristic line and transforms the basis signature to approximate a repetition of the visual pattern along the central line. The data representing at least one of the characteristic line, the central line, the patterns, the basis signature and the transforms of the cross-section are stored in at least one of the data storage devices.
In still another aspect of the invention, computer executable code causes the computing device to identify at least one central line approximating a shape of a characteristic line and to subdivide the central line into subpieces, based on a predetermined length. The computing device further identifies pixels located within a characteristic strip corresponding to each of the subpieces and defines each of the pixels at least according to its distance from the central line and a brightness parameter. The computing device then derives a cross-section at each of the subpieces based on the defined pixels, forms a quadratic difference between each derived cross-section and the cross-section derived from the next subpiece, minimizes the quadratic differences with respect to the parameters of a fitting transformation and identifies a minimized fitting transformation of each derived cross-section and the cross-section derived from the next subpiece. Multiple fitting transformations are composed from the plurality of minimized fitting transformations and interpolated along the corresponding line segment.
The computer executable code then causes the computing device to derive a fitting path from the interpolated fitting transformations and redefine each of the pixels according to a distance from the central line corrected according to the fitting path and one of a brightness and a color parameter corrected according to the fitting path. A corrected cross-section at each of the subpieces is derived based on the redefined pixels. The computing device then identifies an (e.g.) geometrically central point of the corrected cross-section and applies the fitting path to the central point to derive a corrected central line. Data representing at least one of the uniform characteristic line, the central line, the plurality of fitting transformations, the fitting path, the empirical cross-section and the corrected cross-section are stored in one or more data storage devices.
The computing apparatus implementing representation of an image can alternatively include an image reading device for reading and storing the image, an interface device for enabling a user interface, a program module that receives and executes computer readable code, and a model storage device that stores characteristic line model data representing the image. The program module detects multiple edges and/or ridges on the image stored in the image reading device. The program module then detects adjacencies among each of the edges and ridges, interprets common adjacencies as characteristic lines and determines a central line corresponding to each of the characteristic lines. The central line approximates the shape of the characteristic line. The program module further detects cross-sections corresponding to each point along the central line. The cross-sections include one or more geometric parameters and one or more brightness parameters.
The program module can also subdivide each of the edges and ridges into corresponding spline segments. The program module then evaluates each of the spline segments, and identifies adjacent spline segments and at least one adjacency interval on each of multiple edge components corresponding to the edges.
In another aspect of the invention, a program module of the computing apparatus detects edges on the image and subdivides each edge into corresponding spline segments. It evaluates each of the spline segments and identifies adjacent spline segments and connects, with an adjacency pointer, a midpoint of the evaluated spline segment with a midpoint of each of the corresponding adjacent spline segments. This creates multiple adjacency couples. The program module then identifies adjacency intervals as continuous chains of adjacent couples, identifies a central point of each adjacency pointer within each adjacency couple, and joins the central points of each adjacency pointer within each adjacency interval to form a central line corresponding to the characteristic line. The program module then detects cross-sections corresponding to each point along the central line. Each of the cross-sections includes one or more geometric parameters and one or more brightness parameters.
The program module determines a basis cross-section representative of the characteristic line, determines a fitting path corresponding to the cross-sections and assembles a characteristic line model representing the characteristic line. The fitting path includes a transformation of the basis cross-section to the cross-sections of the points along the central line. The characteristic line model includes data representing the central line, the basis cross-section and the fitting path. The data representing one or more of the characteristic lines, the characteristic line model, the central line, the basis cross-section and the fitting path are stored in one or more data storage devices.
According to another aspect of the invention, a program module identifies an empirical cross-section of one or more points of a line on the image and determines whether the line approximates the shape of a uniform characteristic line. If so, the program module identifies a fitting path, a corrected cross-section and a central line of the uniform characteristic line. The data representing one or more of the uniform characteristic lines, the central line, the fitting path, the empirical cross-section and the corrected cross-section are stored in one or more data storage devices. As with all aspects of the invention, the program module can work in conjunction with the interface device to interact with a user in executing the invention.